1. Field of the Invention
The present invention relates to an encoding apparatus, an encoding method, a program for the encoding method, and a recording medium having the program for the encoding method recorded thereon, and is applicable to encoding apparatuses compliant with, e.g., H.264 and MPEG-4 Part 10 (Advanced Video Coding). The present invention reduces computational complexity required for selection of a best prediction mode, in a case where encoding processing is performed by detecting a prediction mode suitable for intra prediction from best prediction modes detected at different prediction value generation units, and when the encoding processing is performed on image data by selecting the best prediction mode from a multitude of prediction modes, while detecting the best prediction modes based on the different prediction value generation units by utilizing one of best prediction mode detecting processing for the other best prediction mode detecting processing.
2. Description of Related Art
In recent years, for transmission and recording of moving images at broadcasting stations, ordinary homes, and the like, apparatuses capable of efficiently transmitting and storing the image data by effectively utilizing redundancy of the image data are becoming popular. Such an apparatus which is compliant with, e.g., MPEG (Moving Picture Experts Group) effectively compresses the image data by utilizing orthogonal transforms, such as Discrete Cosine Transform, and motion compensation.
MPEG2 (ISO/IEC 13818-2) being one of data compression schemes of this type was defined as a general-purpose image encoding scheme. MPEG2 is defined as compatible with both interlace scanning and sequential scanning, as well as with both standard-resolution images and high-definition images. Presently, MPEG2 is widely used for a wide range of applications including both for professional use and consumer use. Specifically, according to MPEG2, e.g., 720×480 pixel image data based on the standard resolution and image data of the interlace scanning scheme can be compressed to a bit rate of 4 to 8 [Mbps]. Further, e.g., 1920×1088 pixel image data based on the high resolution and image data of the interlace scanning scheme can be compressed to a bit rate of 18 to 22 [Mbps], whereby high compressibility with high image quality may be maintained.
However, MPEG2 is a high image quality encoding scheme suitable for broadcasting applications, and hence is not compatible with high compression rate encoding scheme having codes less than codes of MPEG1. Meanwhile, as portable terminals have become popular in recent years, more needs for high compression rate encoding schemes having less codes than codes of MPEG1 are expected. Thus, standards for MPEG4-based encoding schemes were approved as international standard by ISO/IEC (International Organization for Standardization/International Electrotechnical Commission) 14496-2 on December 1998.
Also, as such a data compression scheme, H26L (ITU-T Q6/16 VCEG) which was initially intended for image encoding for videoconferencing is standardized. The H26L has more computational complexity compared to that of MPEG2 and MPEG4, but can maintain encoding efficiency higher than that of MPEG2 and MPEG4. Further, as part of MPEG4 activities, standardization of an encoding scheme for ensuring higher encoding efficiency by infusing various functions based on the H26L was promoted as Joint Model of Enhanced-Compression Video Coding. The scheme was set as an international standard entitled “H.264 and MPEG-4 Part 10 (Advanced Video Coding)”on March 2003. The standard is hereinafter referred to as “JVT standard” in this specification.
FIG. 5 is a block diagram showing an encoding apparatus compliant with the JVT standard. An encoding apparatus 1 selects a best prediction mode from a plurality of intra prediction modes and a plurality of inter prediction modes, and generates difference data (prediction error data) D2 by subtracting prediction values based on the selected prediction mode from image data D1. Also, the encoding apparatus 1 performs orthogonal transform processing, quantization processing, and variable length encoding processing on the difference data D2 to output encoded data D5.
In the encoding apparatus 1, analog-to-digital conversion circuit (A/D) 2 outputs the image data D1 by performing analog/digital conversion processing on a video signal S1. A screen sorting buffer 3 inputs the image data D1 outputted from the analog/digital conversion circuit 2, sorts frames of the image data D1, based on a GOP (Group of Pictures) structure for encoding processing by the encoding apparatus 1, and outputs the sorted frames.
A subtraction circuit 4 receives the image data D1 outputted from this screen sorting buffer 3, and, in intra encoding, subtracts prediction values outputted from an intra prediction circuit 5 from this image data D1, and outputs the difference data D2. Also, in inter encoding, prediction values are inputted from a motion prediction/compensation circuit 6, and the prediction values are subtracted from the image data D1 to output the difference data D2.
An orthogonal transform circuit 7 processes the output data D2 from the subtraction circuit 4 by orthogonal transform processings, such as Discrete Cosine Transform or Karhunen-Loeve Transform, and outputs coefficient data D3 being a processing result. A quantization circuit 8 quantizes the coefficient data D3 in accordance with a quantization scale by rate control of a rate control circuit 9, and outputs the quantized coefficient data D3. An invertible encoding circuit 10 performs invertible encoding processing by variable length encoding, arithmetic encoding, and the like on data outputted from the quantization circuit 8, and generates output data D4. Also, the invertible encoding circuit 10 acquires information on intra encoding, and information on inter encoding, and the like from the intra prediction circuit 5 and the motion prediction/compensation circuit 6, and sets the acquired information to header information of the output data D4.
A storage buffer 11 stores the output data D4 from the invertible encoding circuit 10, and outputs the data D4 at a transmission rate of a subsequent transmission channel. The rate control circuit 9 monitors an amount of codes occurring from the encoding processing by monitoring a remaining space in the storage buffer 11, and switches quantization scales of the quantization circuit 8 on the basis of a monitoring result, and controls the amount of codes occurring by the encoding apparatus 1.
An inverse quantization circuit 13 performs inverse quantization processing on the output data from the quantization circuit 8, and decodes the inputted data of the quantization circuit 8. An inverse orthogonal conversion circuit 14 performs inverse orthogonal conversion processing on output data from the inverse quantization circuit 13, and decodes the input data D2 of the orthogonal conversion circuit 7. The encoding apparatus 1 adds prediction values corresponding to output data from the inverse orthogonal conversion circuit 14, by use of an addition circuit (not shown), and decodes the input data of the subtraction circuit 4. A deblock filter 15 removes block distortion from output data from this addition circuit, and outputs the resultant data. A frame memory 16 records and holds the output data from the deblock filter 15 as reference image information.
The motion prediction/compensation circuit 6 detects, in inter encoding, a motion vector MV of the image data outputted from the image sorting buffer 3 based on a prediction frame by the reference image information stored in the frame memory 16, and detects a best prediction mode in the inter prediction mode. Further, when inter encoding is selected, the motion prediction/compensation circuit 6 motion-compensates the reference image information stored in the frame memory 16 by use of the corresponding motion vector MV, based on the best prediction mode, generates prediction image information, and outputs prediction values based on the prediction image information, to the subtraction circuit 4.
The intra prediction circuit 5 detects, in intra encoding, a best prediction mode in the intra prediction mode on the basis of input data of the frame memory 16. Further, when intra encoding is selected, the intra prediction circuit 5 generates prediction values of prediction image information from the input data of the frame memory 16 on the basis of the best prediction mode, and outputs the generated prediction values to the subtraction circuit 4.
In the encoding apparatus 1, a prediction mode therein is selected from the best prediction modes detected by the intra prediction circuit 5 and the motion prediction/compensation circuit 6, according to a picture for processing associated with the GOP structure, and then based on the selection result, the difference data D2 is selectively generated at the subtraction circuit 4 by the prediction values from the intra prediction circuit 5 or the motion prediction/compensation circuit 6.
FIG. 6 is a block diagram showing a decoder compliant with the JVT standard. In the decoder 20, a storage buffer 21 temporarily stores the encoded data D5 inputted via the transmission channel, and outputs the data. An invertible decoding circuit 22 processes the output data from the storage buffer 21 by variable length decoding, arithmetic decoding, and the like, and decodes the input data of the invertible encoding circuit 10 in the encoding apparatus 1. Also, at this time, if the output data is intra-encoded data, the circuit 22 decodes the intra prediction mode information stored in the header and outputs decoded information to an intra prediction circuit 23. Meanwhile, if the output data is inter-encoded data, the circuit 22 decodes the information about the motion vector stored in the header, and outputs decoded information to a motion prediction/compensation circuit 24.
An inverse quantization circuit 25 performs inverse quantization processing on the output data from the invertible decoding circuit 22, and decodes the coefficient data D3 inputted to the quantization circuit 8 of the encoding apparatus 1. An inverse orthogonal conversion circuit 26 inputs coefficient data outputted from the inverse quantization circuit 25, and performs inverse orthogonal conversion processing thereon, and decodes the difference data D2 inputted to the orthogonal conversion circuit 7 of the encoding apparatus 1.
In intra encoding, an addition circuit 27 inputs the difference data D2 outputted from the inverse orthogonal conversion circuit 26, and adds prediction values of prediction image generated at the intra prediction circuit 23 and outputs the resultant data. On the other hand, in inter encoding, prediction values of prediction image outputted from the motion prediction/compensation circuit 24 are added, and the resultant data is outputted. As a result, the addition circuit 27 decodes the input data of the subtraction circuit 4 in the encoding apparatus 1.
A deblock filter 28 removes block distortion from the output data of the addition circuit 27, and outputs resultant data. A screen sorting buffer 29 sorts frames of image data outputted from the deblock filter 28 according to the GOP structure, and outputs the sorted frames. A digital/analog conversion circuit (D/A) 30 performs digital/analog conversion processing on the output data from the screen sorting buffer 29, and outputs the converted data to the original video signal S1.
A frame memory 31 records and holds the output data from the deblock filter 28 as reference image information. The motion prediction/compensation circuit 24 motion-compensates the reference image information stored in the frame memory 31 on the basis of the motion vector information notified from the invertible decoding circuit 22, in inter encoding, generates prediction values, and outputs the prediction values to the addition circuit 27. The intra perdition circuit 23 generates prediction values from the input data of the frame memory 31 on the basis of intra prediction modes notified from the invertible decoding circuit 22, in intra encoding, and outputs the prediction values to the addition circuit 27.
In the JVT standard, three intra prediction modes are prepared: an intra 4×4 mode, an intra 8×8 mode, and an intra 16×16 mode. In the intra 4×4 mode, a block of 4 pixels×4 pixels is an orthogonal conversion processing unit, and one of the orthogonal conversion processing is a prediction value generation unit in the intra prediction circuit 5. Also, in the intra 16×16 mode, a block of 4 pixels×4 pixels is an orthogonal conversion processing unit, and 4×4 blocks (a block of 16 pixels×16 pixels) of orthogonal conversion processing of 4 pixels×4 pixels is set to be a prediction value generation unit. Meanwhile, in the intra 8×8 mode, similarly to MPEG2, a block of 8 pixels×8 pixels is an orthogonal conversion processing unit, and also serves as a prediction value generation unit. The prediction value generation units in the intra 4×4 mode, intra 8×8 mode, and intra 16×16 mode are hereinafter referred to as “block”, “sub macroblock” and “macroblock”, respectively.
According to the JVT standard, in these intra 4×4 mode, intra 8×8 mode, and intra 16×16 mode, the image data D1 is sequentially processed by a 16 pixel×16 pixel block unit being a macroblock of the intra 16×16 mode. Accordingly, a block formed by halving a 16 pixel×16 pixel block in the intra 16×16 mode both vertically and horizontally is a sub macroblock in the intra 8×8 mode. In the intra 8×8 mode, the sub macroblocks in the 16 pixel×16 pixel macroblock are processed in order of raster scanning. Also, a block formed by quartering a 16 pixel×16 pixel block in the intra 16×16 mode vertically and horizontally is a block in the intra 4×4 mode. In the intra 4×4 mode, the blocks in the 16 pixel×16 pixel macroblock are processed sequentially in order of raster scanning, as indicated by numbers in FIG. 7.
According to the JVT standard, in the intra 4×4 mode or intra 16×16 mode in the intra prediction mode, a prediction value is generated by using pixel values of decoded adjacent blocks or decoded adjacent macroblocks which are to be processed by the deblock filter 15. Also, in the intra 8×8 mode, similarly to MPEG2, a prediction value is generated by use of pixel values of decoded adjacent macroblocks which are already processed by the deblock filter 15.
In the JVT standard, if the video signal S1 is a video signal of the interlaced scanning scheme, encoding processing can be sequentially performed in a field mode or in a frame mode by forming two vertically continuous prediction value generation elements as a pair (hereinafter referred to as “macroblock pair”), as the processing order is indicated by an arrow in FIG. 8.
In the intra prediction mode, prediction value processings differ with respect to luminance signal depending on intra 4×4 mode, intra 8×8 mode, and intra 16×16 mode. Accordingly, in the following, the processing in the intra 4×4 mode will be described first. It is noted that the processing in the intra 8×8 mode is omitted since the processing is similar to that of MPEG2.
The intra 4×4 mode is applied when “mb part pred mode (mb type, 0)” is equal to “Intra4×4”. In prediction value generation processing, luminance signal prediction values for a block for prediction value generation are generated by use of “prev intra4×4 pred mode flag”, “rem intra4×4 pred mode (if available)”, and pre-processed pixel values “(if available)” by the deblock filter of a peripheral luminance “block” as input parameters.
Here, when a value for “adaptive frame field flag” is 0 in the intra 4×4 mode, in the prediction value generation processing, processing for judging as to whether intra prediction of the block is “available” or “not available” is performed. In the judgment processing, as shown in FIG. 9, luminance pixel values of decoded pixels A-M contained in blocks adjacent to the block are inputted, and whether the pixel values of the adjacent pixels A-M are “available” or not with respect to a block of pixels a-p for processing is checked.
Here, a block of 4 pixels×4 pixels for prediction value generation is defined as “4×4LumaBlkLoc”, and a position of an upper left pixel value of this block is defined as indexed by “4×4LumaBlckIdx”. Accordingly, the block of pixels a-p in FIG. 9 is “4×4LumaBlkLoc”, and “4×4LumaBlkIdx” indicates a position of the pixel labeled a. Also, a position (x,y) of the pixel d is indicated by
“x:4×4LumaBlkLoc[4×4LumaBlkIdx][0]+3, y:4×4LumaBlkLoc[4×4LumaBlkIdx][1]”, and a position (x,y) of the pixel A is indicated by
“x:4×4LumaBlkLoc[4×4LumaBlkIdx][0], y:4×4LumaBlkLoc[4×4LumaBlkIdx][1]−1”.
The pixel value of adjacent pixels A-M is judged as “not available”, when the pixel is not within a picture or is not within a slice (condition 1), when the pixel belongs to a block to be processed later than the block for prediction value generation, in decoding processing (condition 2), or when “constrained intra pred flag=0” and the block belongs to an inter macroblock (condition 3). Even if the pixels E-H satisfy any of the conditions 1 to 3, the pixels E-H are judged as “available” by applying a pixel value of the pixel D when the pixel D is “available”.
If “mb adaptive frame field flag” is value 1 and “field pic flag” is value 0, the adjacent pixels A-M are defined in the same way as when value of “mb adaptive frame field flag” is 0. Also, if the block is “field decoding mode” and is “top fieldmacroblock”, the adjacent pixels are defined as indicated by the following formula.
[Formula 1]A:x=4×4LumaBlkLoc[4×4LumaBlkIdx][0]y=4×4LumaBlkLoc[4×4LumaBlkIdx][1]−2I:x=4×4LumaBlkLoc[4×4LumaBlkIdx][0]−1y=4×4LumaBlkLoc[4×4LumaBlkIdx][1]  (1)
Further, when the block is “field decoding mode” and is “bottom field macroblock”, the adjacent pixels are defined as indicated by the following formula.
[Formula 2]A:x=4×4LumaBlkLoc[4×4LumaBlkIdx][0]y=4×4LumaBlkLoc[4×4LumaBlkIdx][1]−1I:x=4×4LumaBlkLoc[4×4LumaBlkIdx][0]−1y=4×4LumaBlkLoc[4×4LumaBlkIdx][1]  (2)
A plurality of prediction modes as shown in FIG. 10 are prepared for the intra 4×4 mode, and applicable prediction modes vary according to a judgment processing result as to whether the above-described adjacent pixels are “available”or “not available”. Prediction directions when values of “Intra4×4LumaPredMode[4×4LumaBlkIdx]” are 0, 1-8 are indicated in FIG. 11 by comparison with FIG. 10. Specific prediction values of the respective prediction modes are described in detail with reference to decoding processing.
As shown in FIG. 12, macroblocks positioned above and left of a macroblock to be processed are highly relevant with the macroblock for processing. Thus, in the JVT standard, a technique by which a prediction direction of the target macroblock is predicted from the prediction directions of the decoded macroblocks positioned above and left of the macroblock is adopted.
In the prediction processing of a prediction direction using prediction directions of the adjacent macroblocks, first, address detection of the adjacent macroblocks and then “availability” verification are executed if value of “adaptive frame field flag” is 0, or if value of “field pic flag” is 1. The address detection and verification processings are executed as follows. An address “MbAddress” of the target macroblock is inputted. An address “MbAddressA” of a macroblock positioned above the target macroblock and an address “MbAddressB” of a macroblock positioned left of the target macroblock are detected. Then, “availability” is judged for the macroblocks positioned above and left of the target macroblock.
Here, a macroblock having an address “MbAddress” is judged as “not available”, if conditions 1 to 4 are satisfied with respect to address MbAddress of the macroblock: “MbAddress”<0 (condition 1); “MbAddress”>“MaxMbAddress−1” (condition 2); the macroblock specified by “MbAddress” belongs to a different slice (condition 3); or the macroblock specified by “MbAddress” is not decoded yet (condition 4).
This judgment processing is applied to the above- and left-positioned macroblocks to judge whether available or not available. In macroblock pair-based processing, an address “MbPairAddressA” of a macroblock pair to which the left-positioned macroblock belongs is an address “MbPairAddress−1” of a macroblock pair to which the macroblock for processing belongs, whereas an address “MbPairAddressB”of a macroblock pair to which the above-positioned macroblock belongs is an address “MbPairAddress−(frame width in mbs minus1+1)” of the macroblock pair to which the macroblock for processing belongs.
Based on the macroblock judgment result, the encoding apparatus performs the address detection and the “availability” verification of the adjacent macroblocks as follows. An input parameter of the processing is “MbAddressA”and an output is a value (four types) of a variable “ExtIntra4×4LumaPred”. In the encoding apparatus, the variable “ExtIntra4×4LumaPred” is transmitted when a prediction direction is predicted from the adjacent macroblocks.
Here, when a macroblock (a macroblock indexed by “MbAddressA”) which is positioned at left of the macroblock is “available” and “mb type” of the macroblock indexed by “MbAddressA” is “I 4×4” or “SI”, a value of “ExtIntra4×4LumaPredMode” is obtained by the following processings. Here, “Intra4×4LumaPredMode” is a value assigned to the macroblock indexed by “MbAddressA”.
[Formula 3]for(i=0, i<4, i++)ExtIntra4×4LumaPredMode[(i+1)*5]=Intra4×4LumaPredMode[4×4LumaBlkScan(3,i)]  (3)
Further, when the macroblock indexed by “MbAddressA” is not “available” or its “mb type” is neither “I 4×4” nor “SI”, the value of “ExtIntra4×4LumaPredMode” is obtained by the following processings.
[Formula 4]for(i=0, i<4, i++)ExtIntra4×4LumaPredMode[(i+1)*5]=2  (4)
If a macroblock (a macroblock indexed by “MbAddressB”) positioned above the macroblockI is “available” and “mb type”of a macroblock indexed by “MbAddressB” is “I 4×4” or “SI”, a value of “ExtIntra4×4LumaPredMode” is obtained by the following processings. Here, “Intra4×4LumaPredMode” is a value assigned to the macroblock indexed by “MbAddressB”.
[Formula 5]for(i=0, i<4, i++)ExtIntra4×4LumaPredMode[i+1]=Intra4×4LumaPredMode[4×4LumaBlkScan(i,3)]  (5)
Further, if a macroblock indexed by “MbAddressB” is not “available” or its “mb type” is neither “I 4×4” nor “SI”, the value of “ExtIntra4×4LumaPredMode” is obtained by the following processings∘
[Formula 6]for(i=0, i<4, i++)ExtIntra4×4LumaPredMode[i+1]=2  (6)
Further, in the case of the macroblock pair-based processing described above with reference to FIG. 7, in the encoding apparatus, information about an intra prediction mode of an adjacent macroblock pair is extracted and transmitted. Here, if value of “mb adaptive frame field flag” of the macroblock is 1 and value of “fieldpic flag” is 0, the processing is executed as follows.
First, when the macroblock pair is “frame mode”, “ExtIntra4×4LumaPredModeTop” and “ExtIntra4×4LumaPredModeBottom” (a total of 8 types) for the macroblock are obtained from “MbPairAddressA” and “MbPairAddressB” with respect to each of “top macroblock” and “bottom macroblock”.
Here, regarding “Top macroblock”, “ExtIntra4×4PredModeTop” and “ExtIntra4×4PredModeTop” are obtained from Formulae (3) and (5). Also, regarding “Bottom Macroblock”, “ExtIntra4×4PredModeTop” and “ExtIntra4×4PredModeTop” are obtained by Formulae (3) and (5). In the above cases, “MbPairAddressA” and “MbPairAddressB” are respectively applied to “MbAddressA” and “MbAddressB” in Formulae (3) and (5).
Further, when the macroblock pair is “field mode”, “ExtIntra4×4LumaPredModeTop” and “ExtIntra4×4LumaPredModeBottom” (a total of eight types) for the macroblock are similarly obtained from “MbPairAddressA” and “MbPairAddressB” for each of “top macroblock” and “bottom macroblock”.
Here, for the adjacent macroblock pair “MbPairAddressA”, both “ExtIntra4×4LumaPredModeTop” and “ExtIntra4×4LumaPredModeBottom” are obtained by Formula (3). Here, “MbPairAddressA” is applied to “MbAddressA” in Formula (3).
It is noted that if the adjacent macroblock pair “MbPairAddressB” is “fieldmode”, or if the adjacent macroblock pair “MbPairAddressB” is not “available” and the macroblock pair is “top macroblock”, “ExtIntra4×4LumaPredModeTop” is obtained by Formula (5). In this case, “top macroblock” of “MB Pair” indexed by “MBPairAddressB” is applied to “MBAddressB” in Formula (5).
If the adjacent macroblock pair “MbPairAddressB” is “field mode”, or if the adjacent macroblock pair “MbPairAddressB” is not “available” and the macroblock pair is “bottom macroblock”, “ExtIntra4×4LumaPredModeBottom” is obtained by Formula (5). In this case, “top macroblock” of “MB Pair” indexed by “MBPairAddressB” is applied to “MBAddressB” in Formula (5).
Further, when the adjacent macroblock pair “MbPairAddressB” is “frame mode”, with respect to “top macroblock” in the macroblock pair, “ExtIntra4×4LumaPredModeTop” is obtained by application of Formula (5). However, “top macroblock” of the macroblock pair indexed by “MBPairAddressB” is applied to “MBAddressB” in Formula (5). Also, for “bottom macroblock” in the macroblock pair, “ExtIntra4×4LumaPredModeBottom” is obtained by application of Formula (5). However, “bottom macroblock” of the macroblock pair indexed by “MBPairAddressB” is applied to “MBAddressB” in Formula (5).
FIGS. 13A to 13D are diagrams showing relation between macroblock pairs based on results of the processing performed when the macroblock pairs are “field mode”.
Decoding processing for “Intra4×4LumaPredMode” for macroblocks is executed as follows. The processing here is applied in a case where value of “adaptive frame field flag” is 1, or a case where value of “field pic flag” is 1, and is described with the following pseudo codes which use “prev intra4×4 pred mode flag”, “rem intra4×4 pred mode”, and “ExtIntra4×4LumaPredMode”.
                    [                  Formula          ⁢                                          ⁢          7                ]                                                            for        ⁢                                  ⁢                              (                                                            4                  ×                  4                  ⁢                  LumaBlkldx                                =                0                            ,                              4                ×                4                ⁢                LumaBlkldx                ⁢                                                                  ×                16                            ,                              4                ×                4                ⁢                                  LumaBlkldx                  ++                                                      )                    [                                          ⁢                                          ⁢                      i            =                                                            4                  ×                  4                  ⁢                  LumaBlkldx                                +                                  RasterTo                  ⁢                                                                          ⁢                  4                  ×                  4                  ⁢                                      LumaBlkOffset                    ⁡                                          (                                              4                        ×                        4                        ⁢                        LumaBlkldx                                            )                                                        ⁢                                                                          ⁢                                                                          ⁢                  Ext                  ⁢                                                                          ⁢                  4                  ×                  4                  ⁢                                                                          ⁢                  LumaBlkldx                                            =                                                                    5                    *                                          (                                                                        i                          /                          4                                                +                        1                                            )                                                        +                                      (                                          i                      ⁢                                                                                          ⁢                      %                      ⁢                                                                                          ⁢                      4                                        )                                    +                                      1                    ⁢                                                                                  ⁢                                                                                  ⁢                    PredIntra                    ⁢                                                                                  ⁢                    4                    ×                    4                    ⁢                    LumaPredMode                                                  ⁢                                                                  ⁢                                                                  =                                                                            Min                      ⁡                                              (                                                                              ExtIntra                            ⁢                                                                                                                  ⁢                            4                            ×                            4                            ⁢                                                          LumaPredMode                              ⁡                                                              [                                                                                                      Ext                                    ⁢                                                                                                                                                  ⁢                                    4                                    ×                                    4                                    ⁢                                    LumaBlkldx                                                                    -                                  1                                                                ]                                                                                                              ,                                                                                                          ⁢                                                                                                          ⁢                                                      ExtIntra                            ⁢                                                                                                                  ⁢                            4                            ×                            4                            ⁢                                                                                                                  ⁢                                                          LumaPredMode                              ⁡                                                              [                                                                  Ext                                  ⁢                                                                                                                                          ⁢                                  4                                  ×                                  4                                  ⁢                                  LumaBlkldx                                  ⁢                                                                                                                                          ⁢                                  5                                                                ]                                                                                                                                    )                                                              ⁢                                                                                  ⁢                                                                                  ⁢                    if                    ⁢                                                                                  ⁢                                          (                                              prev_intra4                        ×                        4                        ⁢                        _pred                        ⁢                                                                                                  ⁢                        mode                        ⁢                                                                                                  ⁢                                                  flag                          ⁡                                                      [                                                          4                              ×                              4                              ⁢                                                                                                                          ⁢                              LumaBlkldx                                                        ]                                                                                              )                                        ⁢                                                                                  ⁢                                                                                  ⁢                    Intra                    ⁢                                                                                  ⁢                    4                    ×                    4                    ⁢                                                                                  ⁢                                          LumaPredMode                      ⁡                                              [                                                  4                          ×                          4                          ⁢                          LumaBlkldx                                                ]                                                                              =                                                            PredIntra                      ⁢                                                                                          ⁢                      4                      ×                      4                      ⁢                      LumaPredMode                      ⁢                                                                                          ⁢                                              else                        ⁢                                                                                                  [                                                                                                  ⁢                                                                              if                            ⁢                                                                                                                  ⁢                                                          (                                                                                                rem_intra                                  ⁢                                                                                                                                          ⁢                                  4                                  ×                                  4                                  ⁢                                  _pred                                  ⁢                                                                      _mode                                    ⁡                                                                          [                                                                              4                                        ×                                        4                                        ⁢                                        LumaBlkldx                                                                            ]                                                                                                                                      <                                                                  PredIntra                                  ⁢                                                                                                                                          ⁢                                  4                                  ×                                  4                                  ⁢                                  LumaPredMode                                                                                            )                                                        ⁢                                                                                                                  ⁢                                                                                                                  ⁢                            Intra                            ⁢                                                                                                                  ⁢                            4                            ×                            4                            ⁢                                                          LumaPredMode                              ⁡                                                              [                                                                  4                                  ×                                  4                                  ⁢                                  LumaBlkldx                                                                ]                                                                                                              ⁢                                                                                                          ⁢                                                                                                          =                                                                                    rem_intra4                              ×                              4                              ⁢                              _pred                              ⁢                                                              _mode                                ⁡                                                                  [                                                                      4                                    ×                                    4                                    ⁢                                    LumaBlkldx                                                                    ]                                                                                            ⁢                                                                                                                          ⁢                              else                              ⁢                                                                                                                          ⁢                                                                                                                          ⁢                              Intra                              ⁢                                                                                                                          ⁢                              4                              ×                              4                              ⁢                                                              LumaPredMode                                ⁡                                                                  [                                                                      4                                    ×                                    4                                    ⁢                                    LumaBlkldx                                                                    ]                                                                                                                      ⁢                                                                                                                  ⁢                                                                                                                  =                                                                                          rem_intra4                                ×                                4                                ⁢                                _pred                                ⁢                                                                  _mode                                  ⁡                                                                      [                                                                          4                                      ×                                      4                                      ⁢                                      LumaBlkldx                                                                        ]                                                                                                                              +                              1                                                                                                      ⁢                                                                                                  ]                                            ⁢                                                                                          ⁢                      ExtIntra                      ⁢                                                                                          ⁢                      4                      ×                      4                      ⁢                                              LumaPredMode                        ⁡                                                  [                                                      Ext                            ⁢                                                                                                                  ⁢                            4                            ×                            4                            ⁢                            LumaBlkldx                                                    ]                                                                                      ⁢                                                                                  =                                          Intra                      ⁢                                                                                          ⁢                      4                      ×                      4                      ⁢                                              LumaPredMode                        ⁡                                                  [                                                      4                            ×                            4                            ⁢                            LumaBlkldx                                                    ]                                                                                                                                                  ⁢                                          ]                                    (        7        )            
Meanwhile, decoding processing for “Intra4×4LumaPredMode” for the macroblock pair described above with reference to FIG. 7 is executed as follows. The processing here is applied if value of “mb adaptive frame field flag” is 1 and value of “field pic flag” is 0. This processing is executed by processing of the pseudo codes in Formula (7) which uses “prev intra4×4 pred mode flag”, “rem intra4×4 pred mode”, and “ExtIntra4×4LumaPredModeTop” for “top macroblock”of the macroblock pair. The obtained “Intra4×4LumaPredMode”is assigned to “top macroblock” of the macroblock pair. Also, “Intra4×4LumaPredMode” is obtained by processing of the pseudo codes in Formula (7) which uses “prev intra4×4 pred mode flag”, “rem intra4×4 pred mode”, and “ExtIntra4×4LumaModePredTop”for “bottom macroblock” of the macroblock pair, and is assigned to “bottom macroblock” of the macroblock pair.
Further, in decoding processing for intra prediction in the intra 4×4 mode, prediction pixel values on a block specified by “4×4LumaBlkIdx”, using the pixel values of the adjacent pixels A-M and “Intra4×4LumaPredMode[4×4LumaBlkIdx]” defined for 4×4 blocks are obtained.
Here, “Vertical” prediction is applied when value of “Intra4×4LumaPredMode[4×4LumaBlkIdx]” is 0, and is applied only when the adjacent pixels A-D are “available”. The respective prediction values are indicated by the following formula.
                    [                  Formula          ⁢                                          ⁢          8                ]                                                                                                a              ,              e              ,              i              ,                              m                :                A                                                                                        b              ,              f              ,              j              ,                              n                :                B                                                                                        c              ,              g              ,              k              ,                              o                :                C                                                                                        d              ,              h              ,              l              ,                              p                :                D                                                                        (        8        )            
Further, “Horizontal” prediction is applied when value of “Intra4×4LumaPredMode[4×4LumaBlkIdx]” is 1, and is applied only when the adjacent pixels I-L are “available”. The respective prediction values are indicated by the following formula.
                    [                  Formula          ⁢                                          ⁢          9                ]                                                                                                a              ,              b              ,              c              ,                              d                :                I                            ,                                                                          e              ,              f              ,              g              ,                              h                :                J                            ,                                                                          i              ,              j              ,              k              ,                              l                :                K                            ,                                                                          m              ,              n              ,              o              ,                              p                :                L                            ,                                                          (        9        )            
Further, “DC” prediction is applied when value of “Intra4×4LumaPredMode[4×4LumaBlkIdx]” is 2, and when all the adjacent pixels A-L are “available”, prediction values are indicated by the following formula.
[Formula 10](A+B+C+D+I+J+K+L+4)>>3  (10)
On the other hand, if all the adjacent pixels A-D are “not available”, the prediction values are indicated by the following formula.
[Formula 11](I+J+K+L+2)>>2  (11)
Further, if all the adjacent pixels I-L are “not available”, the prediction values are indicated by the following formula.
[Formula 12](A+B+C+D+2)>2  (12)
Further, when all the adjacent pixels A-L are “not available”, the prediction values are set to be 128.
On the other hand, “Diagonal Down Left” prediction is applied when value of “Intra4×4LumaPredMode[4×4LumaBlkIdx]”is 3, is applied only when the adjacent pixels A-M are “available”, and the prediction values are indicated by the following formula.
                    [                  Formula          ⁢                                          ⁢          13                ]                                                                                                a              :                                                                          (                                  A                  +                                      2                    ⁢                    B                                    +                  C                  +                  2                                )                            >>              2                                                                          b              ,                              e                :                                                                                        (                                  B                  +                                      2                    ⁢                    C                                    +                  D                  +                  2                                )                            >>              2                                                                          c              ,              f              ,                              i                :                                                                                        (                                  C                  +                                      2                    ⁢                    D                                    +                  E                  +                  2                                )                            >>              2                                                                          d              ,              g              ,              j              ,                              m                :                                                                                        (                                  D                  +                                      2                    ⁢                    E                                    +                  F                  +                  2                                )                            >>              2                                                                          h              ,              k              ,                              n                :                                                                                        (                                  E                  +                                      2                    ⁢                    F                                    +                  G                  +                  2                                )                            >>              2                                                                          l              ,                              o                :                                                                                        (                                  F                  +                                      2                    ⁢                    G                                    +                  H                  +                  2                                )                            >>              2                                                                          p              :                                                                          (                                  G                  +                                      3                    ⁢                    H                                    +                  2                                )                            >>              2                                                          (        13        )            
Further, “Diagonal Down Right” prediction is applied if “Intra4×4LumaPredMode[4×4LumaBlkIdx]” is 4, and is applied only if the adjacent pixels A-Mare “available”. The prediction values are indicated by the following formula.
                    [                  Formula          ⁢                                          ⁢          14                ]                                                                                                m              :                                                                          (                                  J                  +                                      2                    ⁢                    K                                    +                  L                  +                  2                                )                            >>              2                                                                          i              ,                              n                :                                                                                        (                                  I                  +                                      2                    ⁢                    J                                    +                  K                  +                  2                                )                            >>              2                                                                          e              ,              j              ,                              o                :                                                                                        (                                  M                  +                                      2                    ⁢                    I                                    +                  J                  +                  2                                )                            >>              2                                                                          a              ,              f              ,              k              ,                              p                :                                                                                        (                                  A                  +                                      2                    ⁢                    M                                    +                  I                  +                  2                                )                            >>              2                                                                          b              ,              g              ,                              l                :                                                                                        (                                  M                  +                                      2                    ⁢                    A                                    +                  B                  +                  2                                )                            >>              2                                                                          c              ,                              h                :                                                                                        (                                  A                  +                                      2                    ⁢                    B                                    +                  C                  +                  2                                )                            >>              2                                                                          d              :                                                                          (                                  B                  +                                      2                    ⁢                    C                                    +                  D                  +                  2                                )                            >>              2                                                          (        14        )            
Further, “Diagonal Vertical Right” prediction is applied if value of “Intra4×4LumaPredMode[4×4LumaBlkIdx]” is 5, and is applied only if the adjacent pixels A-M are “available”. The prediction values are indicated by the following formula.
                    [                  Formula          ⁢                                          ⁢          15                ]                                                                                                a              ,                              j                :                                                                                        (                                  M                  +                  A                  +                  1                                )                            >>              1                                                                          b              ,                              k                :                                                                                        (                                  A                  +                  B                  +                  1                                )                            >>              1                                                                          c              ,                              l                :                                                                                        (                                  B                  +                  C                  +                  1                                )                            >>              1                                                                          d              :                                                                          (                                  C                  +                  D                  +                  1                                )                            >>              1                                                                          e              ,                              n                :                                                                                        (                                  I                  +                                      2                    ⁢                    M                                    +                  A                  +                  2                                )                            >>              2                                                                          f              ,                              o                :                                                                                        (                                  M                  +                                      2                    ⁢                    A                                    +                  B                  +                  2                                )                            >>              2                                                                          g              ,                              p                :                                                                                        (                                  A                  +                                      2                    ⁢                    B                                    +                  C                  +                  2                                )                            >>              2                                                                          h              :                                                                          (                                  B                  +                                      2                    ⁢                    C                                    +                  D                  +                  2                                )                            >>              2                                                                          i              :                                                                          (                                  M                  +                                      2                    ⁢                    I                                    +                  J                  +                  2                                )                            >>              2                                                                          m              :                                                                          (                                  I                  +                                      2                    ⁢                    J                                    +                  K                  +                  2                                )                            >>              2                                                          (        15        )            
Further, “Horizontal Down” prediction is applied when value of “Intra4×4LumaPredMode[4×4LumaBlkIdx]” is 6, and is applied only when the adjacent pixels A-M are “available”. The prediction values are indicated by the following formula.
                    [                  Formula          ⁢                                          ⁢          16                ]                                                                                                a              ,                              g                :                                                                                        (                                  M                  +                  I                  +                  1                                )                            >>              1                                                                          b              ,                              h                :                                                                                        (                                  I                  +                                      2                    ⁢                                                                                  ⁢                    M                                    +                  A                  +                  2                                )                            >>              2                                                                          c              :                                                                          (                                  M                  +                                      2                    ⁢                                                                                  ⁢                    A                                    +                  B                  +                  2                                )                            >>              2                                                                          d              :                                                                          (                                  A                  +                                      2                    ⁢                                                                                  ⁢                    B                                    +                  C                  +                  2                                )                            >>              2                                                                          e              ,                              k                :                                                                                        (                                  I                  +                  J                  +                  1                                )                            >>              1                                                                          f              ,                              l                :                                                                                        (                                  M                  +                                      2                    ⁢                    I                                    +                  J                  +                  2                                )                            >>              2                                                                          i              ,                              o                :                                                                                        (                                  J                  +                  K                  +                  1                                )                            >>              1                                                                          j              ,                              p                :                                                                                        (                                  I                  +                                      2                    ⁢                    J                                    +                  K                  +                  2                                )                            >>              2                                                                          m              :                                                                          (                                  K                  +                  L                  +                  1                                )                            >>              1                                                                          n              :                                                                          (                                  J                  +                                      2                    ⁢                    K                                    +                  L                  +                  2                                )                            >>              2                                                          (        16        )            
Further, “Vertical Left” prediction is applied when value of “Intra4×4LumaPredMode[4×4LumaBlkIdx]” is 7, and is applied only when the adjacent pixels A-M are “available”. The prediction values are indicated by the following formula.
                    [                  Formula          ⁢                                          ⁢          17                ]                                                                                                a              ⁢                              :                                                                                        (                                  A                  +                  B                  +                  1                                )                            >>              1                                                                          b              ,                              i                ⁢                                  :                                                                                                        (                                  B                  +                  C                  +                  1                                )                            >>              1                                                                          c              ,                              j                ⁢                                  :                                                                                                        (                                  C                  +                  D                  +                  1                                )                            >>              1                                                                          d              ,                              k                ⁢                                  :                                                                                                        (                                  D                  +                  E                  +                  1                                )                            >>              1                                                                          l              ⁢                              :                                                                                        (                                  E                  +                  F                  +                  1                                )                            >>              1                                                                          e              ⁢                              :                                                                                        (                                  A                  +                                      2                    ⁢                    B                                    +                  C                  +                  2                                )                            >>              2                                                                          f              ,                              m                ⁢                                  :                                                                                                        (                                  B                  +                                      2                    ⁢                    C                                    +                  D                  +                  2                                )                            >>              2                                                                          g              ,                              n                ⁢                                  :                                                                                                        (                                  C                  +                                      2                    ⁢                    D                                    +                  E                  +                  2                                )                            >>              2                                                                          h              ,                              o                ⁢                                  :                                                                                                        (                                  D                  +                                      2                    ⁢                    E                                    +                  F                  +                  2                                )                            >>              2                                                                          p              ⁢                              :                                                                                        (                                  E                  +                                      2                    ⁢                    F                                    +                  G                  +                  2                                )                            >>              2                                                          (        17        )            
Further, “Horizontal Up” prediction is applied when value of “Intra4×4LumaPredMode[4×4LumaBlkIdx]” is 8, and is applied only when the adjacent pixels A-M are “available”. The prediction values are indicated by the following formula.
                    [                  Formula          ⁢                                          ⁢          18                ]                                                                                                a              ⁢                              :                                                                                        (                                  I                  +                  J                  +                  1                                )                            >>              1                                                                          b              ⁢                              :                                                                                        (                                  I                  +                                      2                    ⁢                                                                                  ⁢                    J                                    +                  K                  +                  2                                )                            >>              2                                                                          c              ,                              e                ⁢                                  :                                                                                                        (                                  J                  +                  K                  +                  1                                )                            >>              1                                                                          d              ,                              f                ⁢                                  :                                                                                                        (                                  J                  +                                      2                    ⁢                                                                                  ⁢                    K                                    +                  L                  +                  2                                )                            >>              2                                                                          g              ,                              i                ⁢                                  :                                                                                                        (                                  K                  +                  L                  +                  1                                )                            >>              1                                                                          h              ,                              j                ⁢                                  :                                                                                                        (                                  K                  +                                      3                    ⁢                                                                                  ⁢                    L                                    +                  2                                )                            >>              2                                                                          k              ,              l              ,              m              ,              n              ,              o              ,                              p                ⁢                                  :                                                                          L                                              (        18        )            
Processings with respect to the intra 16×16 mode are described next. Here, the intra 16×16 mode is applied when “mb part pred mode(mb type,0) is equal to “Intra16×16”. In the prediction value generation processing, prediction values of luminance signal with respect to the macroblock is generated by using “mb type” for the macroblock and pixel values which are not processed yet by the deblock filter 15 of adjacent pixels of the, as input parameters.
Here, pixel values belonging to the macroblock is represented as P(x,y); x,y=0 to 15. Further, adjacent pixel values are represented as P(x,−1) and P(−1,y); x,y=−1 to 15. If the following condition 1 or 2 is satisfied for the pixel values P(x,−1) and P(−1,y), the pixel value P(x,y) is judged as “not available”. The condition 1 is a case where a prediction value generation source is not present in the picture or in the slice, whereas the condition 2 is a case where the adjacent pixel values belong to a non-intra macroblock and value of “constrained intra pred flag” is 1.
In the intra 16×16 mode, modes 0-3 are defined by judging the pixel value P(x,y). Here, mode 0 is “vertical” prediction, and is applied only if the pixel values P(x,−1); x,y=−1 to 15 are “available”, and the prediction values are indicated by the following formula.
[Formula 19]Pred(x,y)=P(x,−1); x,y=0 . . . 15  (19)
Further, model is “horizontal” prediction, and is applied only if the pixel values P(−1,y); x,y=−1 to 15 are “available”. The prediction values are indicated by the following formula.
[Formula 20]Pred(x,y)=P(−1,y); x,y=0 . . . 15  (20)
Further, mode 2 is “DC” prediction, and when all the pixel values P(x,−1) and P(−1,y);x,y=−1 to 15 are “available”, the prediction values are indicated by the following formula.
                    [                  Formula          ⁢                                          ⁢          21                ]                                                                                                Pred              ⁡                              (                                  x                  ,                  y                                )                                      =                          [                                                                    ∑                                                                  X                        ′                                            =                      0                                        15                                    ⁢                                      P                    ⁡                                          (                                                                        x                          ′                                                ,                                                  -                          1                                                                    )                                                                      +                                                      ∑                                          y                      =                      0                                        15                                    ⁢                                      P                    ⁡                                          (                                                                        -                          1                                                ,                                                  y                          ′                                                                    )                                                                      +                16                            ]                                >>          5                ⁢                                  ⁢        with        ⁢                                  ⁢                  x          ,                      y            =                          0              ⁢                                                          ⁢              …              ⁢                                                          ⁢              15                                                          (        21        )            
Further, in mode 2, if the pixel values P(x,−1);x,y=−1 to 15 are “not available”, the prediction values are indicated by the following formula.
                    [                  Formula          ⁢                                          ⁢          22                ]                                                                                                Pred              ⁡                              (                                  x                  ,                  y                                )                                      =                          [                                                                    ∑                                                                  y                        ′                                            =                      0                                        15                                    ⁢                                      P                    ⁡                                          (                                                                        -                          1                                                ,                                                  y                          ′                                                                    )                                                                      +                8                            ]                                >>          4                ⁢                                  ⁢        with        ⁢                                  ⁢                  x          ,                      y            =                          0              ⁢                                                          ⁢              …              ⁢                                                          ⁢              15                                                          (        22        )            
Further, in mode 2, if the pixel values P(−1,y);x,y=−1 to 15 are “not available”, the prediction values are indicated by the following formula.
                    [                  Formula          ⁢                                          ⁢          23                ]                                                                                                Pred              ⁡                              (                                  x                  ,                  y                                )                                      =                          [                                                                    ∑                                                                  X                        ′                                            =                      0                                        15                                    ⁢                                      P                    ⁡                                          (                                                                        x                          ′                                                ,                                                  -                          1                                                                    )                                                                      +                8                            ]                                >>          4                ⁢                                  ⁢        with        ⁢                                  ⁢                  x          ,                      y            =                          0              ⁢                                                          ⁢              …              ⁢                                                          ⁢              15                                                          (        23        )            
Further, if all the pixel values P(x,−1) and P(−1,y); x,y=−1 to 15 are “not available”, the prediction values are set to be value 128.
On the other hand, mode 3 is “plane” prediction, and is applied only when all the pixel values P(x,−1) and P(−1,y); x,y=−1 to 15 are “available”. The prediction values are indicated by the following formula. It is noted that Clip( ) represents clip processing within a range from 0 to 255.
                    [                  Formula          ⁢                                          ⁢          24                ]                                                                                  Pred            ⁡                          (                              x                ,                y                            )                                =                      Clip            ⁢                                                  ⁢            1            ⁢                          (                                                (                                      a                    +                                          b                      ·                                              (                                                  x                          -                          7                                                )                                                              +                                          c                      ·                                              (                                                  y                          -                          7                                                )                                                              +                    16                                    )                                >>                5                            )                                      ⁢                                  ⁢                  a          =                      16            ·                          (                                                P                  ⁡                                      (                                                                  -                        1                                            ,                      15                                        )                                                  +                                  P                  ⁡                                      (                                          15                      ,                                              -                        1                                                              )                                                              )                                      ⁢                                  ⁢                              b            =                          (                                                5                  ·                  H                                +                32                            )                                >>          6                ⁢                                  ⁢                              c            =                          (                                                5                  ·                  V                                +                32                            )                                >>          6                ⁢                                  ⁢                  H          =                                    ∑                              x                =                1                            8                        ⁢                          x              ·                              (                                                      P                    ⁡                                          (                                                                        7                          +                          x                                                ,                                                  -                          1                                                                    )                                                        -                                      P                    ⁡                                          (                                                                        7                          -                          x                                                ,                                                  -                          1                                                                    )                                                                      )                                                    ⁢                                  ⁢                  V          =                                    ∑                              y                =                1                            8                        ⁢                          y              ·                              (                                                      P                    ⁡                                          (                                                                        -                          1                                                ,                                                  7                          +                          y                                                                    )                                                        -                                      P                    ⁡                                          (                                                                        -                          1                                                ,                                                  7                          -                          y                                                                    )                                                                      )                                                                        (        24        )            
Intra prediction of chrominance signal is described next. Here, intra prediction of chrominance signal is applied only to “I” macroblocks and “SI” macroblocks, and generates chrominance signal prediction values for a macroblock by using “intra chroma pred mode”, and adjacent pixel values which are not yet processed by the deblock filter 15, as input parameters.
Here, a pixel value belonging to the macroblock is represented as P(x,y); x,y=0 to 7. Further, adjacent pixel values are represented as P(x,−1) and P(−1,y);x,y=−1 to 7. It is noted that intra prediction modes with respect to chrominance signals can be set independently from prediction modes of luminance signal. If condition 1 or condition 2 is satisfied for the pixel values P(x,−1) and P(−1,y), the pixel value P(x,y) is judged as “not available”. It is noted that condition 1 is a case where a prediction value generation source is not present in the picture or in the slice, whereas condition 2 is a case where the adjacent pixel values belong to anon-intra macroblock and value of “constrained intra pred flag” is 1.
In the chrominance signal intra prediction mode, modes 0-3 are defined by judgment of the pixel value P(x,y). Here, mode 0 is “DC” prediction, and when P(x,−1) and P(−1,y) are “available”, the prediction values are indicated by the following formula.
                    [                  Formula          ⁢                                          ⁢          25                ]                                                                                                Pred              ⁡                              (                                  x                  ,                  y                                )                                      =                          (                                                (                                                            ∑                                              n                        =                        0                                            7                                        ⁢                                          (                                                                        P                          ⁡                                                      (                                                                                          -                                1                                                            ,                              n                                                        )                                                                          +                                                  P                          ⁡                                                      (                                                          n                              ,                                                              -                                1                                                                                      )                                                                                              )                                                        )                                +                8                            )                                >>          4                ⁢                                  ⁢        with        ⁢                                  ⁢        x        ,                  y          =                      0            ⁢                                                  ⁢            …            ⁢                                                  ⁢            7                                              (        25        )            
Meanwhile, if the pixel value P(−1,y) is “not available”, the prediction values are indicated by the following formula.
                    [                  Formula          ⁢                                          ⁢          26                ]                                                                                                Pred              ⁡                              (                                  x                  ,                  y                                )                                      =                          [                                                (                                                            ∑                                              n                        =                        0                                            7                                        ⁢                                          P                      ⁡                                              (                                                  n                          ,                                                      -                            1                                                                          )                                                                              )                                +                4                            ]                                >>          3                ⁢                                  ⁢        with        ⁢                                  ⁢                  x          ,                      y            =                          0              ⁢                                                          ⁢              …              ⁢                                                          ⁢              7                                                          (        26        )            
Further, if the pixel value P(x,−1) is “not available”, the prediction values are indicated by the following formula.
                    [                  Formula          ⁢                                          ⁢          27                ]                                                                                                Pred              ⁡                              (                                  x                  ,                  y                                )                                      =                          [                                                (                                                            ∑                                              n                        =                        0                                            7                                        ⁢                                          P                      ⁡                                              (                                                                              -                            1                                                    ,                          n                                                )                                                                              )                                +                4                            ]                                >>          3                ⁢                                  ⁢                              with            ⁢                                                  ⁢            x                    ,                      y            =                          0              ⁢                                                          ⁢              …              ⁢                                                          ⁢              7                                                          (        27        )            
Further, if the pixel values P(x, −1) and P(−1,y) are “not available”, the prediction values are set to be value 128.
Further, mode 1 is “horizontal” prediction, and is applied only when the pixel value P(−1,y) is “available”. The prediction values are indicated by the following formula.
[Formula 28]Pred(x,y)=P(−1,y), x,y=0, . . . , 7  (28)
Further, mode 2 is “vertical” prediction, and is applied only when the pixel value P(x,−1) is “available”. The prediction values are indicated by the following formula.
[Formula 29]Pred(x,y)=P(x,−1), x,y=0, . . . , 7  (29)
Further, mode 3 is “plane” prediction, and is applied only when the pixel values P(x,−1) and P(−1,y) are “available”. The prediction values are indicated by the following formula.
                    [                  Formula          ⁢                                          ⁢          30                ]                                                                                                                                  Pred                  ⁡                                      (                                          x                      ,                      y                                        )                                                  =                                  Clip                  ⁢                                                                          ⁢                  1                  ⁢                                      (                                          a                      +                                              b                        ·                                                  (                                                      x                            -                            3                                                    )                                                                    +                                              c                        ·                                                  (                                                      y                            -                            3                                                    )                                                                    +                      16                                        )                                                              >>              5                        ;                    ⁢                                          ⁢                      x            ,                          y              =              0                        ,            …            ⁢                                                  ,            7                    ⁢                                          ⁢                      a            =                          16              ·                              (                                                      P                    ⁡                                          (                                              -                        1.7                                            )                                                        +                                      P                    ⁡                                          (                                              7                        ,                                                  -                          1                                                                    )                                                                      )                                              ⁢                                          ⁢                                    b              =                              (                                                      17                    ·                    H                                    +                  16                                )                                      >>            5                    ⁢                                          ⁢                                    c              =                              (                                                      17                    ·                    V                                    +                  16                                )                                      >>            5                    ⁢                                          ⁢          H          =                                    ∑                              x                =                1                            4                        ⁢                          x              ·                              [                                                      P                    ⁡                                          (                                                                        3                          +                          x                                                ,                                                  -                          1                                                                    )                                                        -                                      P                    ⁡                                          (                                                                        3                          -                          x                                                ,                        1                                            )                                                                      ]                                                    ⁢                                  ⁢                  V          =                                    ∑                              y                =                1                            4                        ⁢                          x              ·                              [                                                      P                    ⁡                                          (                                                                        -                          1                                                ,                                                  3                          +                          y                                                                    )                                                        -                                      P                    ⁡                                          (                                                                        -                          1                                                ,                                                  3                          -                          y                                                                    )                                                                      ]                                                                        (        30        )            
The encoding apparatus selects a best prediction mode from the various prediction modes, and performs encoding processing on the image data D1. Here, Org(i,j) is assumed to be a pixel value on the original image in the 4×4 blocks, and Pred(mode,i,j) is assumed to be a prediction value by the intra prediction mode indicated by mode (i,j). The encoding apparatus sets a prediction mode in which prediction error is minimized by computation processing based on the following formula, as a best prediction mode.
                    [                  Formula          ⁢                                          ⁢          31                ]                                                                      SAD          ⁡                      (            mode            )                          =                              ∑                          i              =              0                        3                    ⁢                                    ∑                              j                =                0                            3                        ⁢                                                                          Org                  ⁡                                      (                                          i                      ,                      j                                        )                                                  -                                  Pred                  ⁡                                      (                                          mode                      ,                      i                      ,                      j                                        )                                                                                                                        (        31        )            
Here, SAD is a function which selects a mode of a minimum value, and as shown by the following formula, SATD(mode) may alternatively be applied in place of SAD.
                                              ⁢                  [                      Formula            ⁢                                                  ⁢            32                    ]                                                                              SATD          ⁡                      (            mode            )                          =                              ∑                          i              =              0                        3                    ⁢                                    ∑                              j                =                0                            3                        ⁢                                                        Hadamard                ⁢                                                                  ⁢                                  (                                                            Org                      ⁢                                              (                                                  i                          ,                          j                                                )                                                              -                                          Pred                      ⁡                                              (                                                  Mode                          ,                          i                          ,                          j                                                )                                                                              )                                                                                                      (        32        )            
Hadamard( ) represents an Hadamard conversion operation, and is executed by multiplying a target matrix by an Hadamard conversion matrix, as indicated by the following formula.
[Formula 33]Hadamard(A)=HTAH  (33)
Noted “H” is the Hadamard conversion matrix, and fourth order matrix is represented by the following formula.
                    [                  Formula          ⁢                                          ⁢          34                ]                                                            H        =                  (                                                    1                                                                                ⁢                  1                                                                                                ⁢                  1                                                                                                ⁢                  1                                                                                    1                                                              -                                    ⁢                  1                                                                                                ⁢                  1                                                                              -                                    ⁢                  1                                                                                    1                                                                                ⁢                  1                                                                              -                                    ⁢                  1                                                                              -                                    ⁢                  1                                                                                    1                                                              -                                    ⁢                  1                                                                              -                                    ⁢                  1                                                                                                ⁢                  1                                                              )                                    (        34        )            
“HT” represents a transposed Hadamard conversion matrix H.
Practically, in the encoding apparatus 1, as shown in FIGS. 14A to 14C, SAD(mode) or SATD(mode) is obtained on a block unit basis of 16 pixel×16 pixel, per prediction mode based on the intra 4×4 mode, intra 8×8 mode, and intra 16×16 mode, or a mode of a minimum value by a cost function in which a header bit component-based codes are added to codes generated by each mode is selected, in order to select a best prediction mode. A relation with macroblocks in each prediction mode is also shown in FIG. 14D.
Alternatively, a header bit in a case where the 16 pixel×16 pixel block is encoded at each intra prediction mode “mode”may be represented as SAD0(mode) or SATD0(mode), and a prediction mode in which a cost value “Cost” represented by the SAD0(mode) or SATD0(mode) is set to be minimum, is assumed to be a best prediction mode. Noted, the cost value “Cost”is represented by the following formula, and QP0 (QP) is a function linking a quantization parameter QP with the quantization scale used for actual quantization. The cost value is a value in each prediction mode obtained by the cost function used in judging a prediction mode, and also is a value as an index indicating the amount of occurring codes. Specifically, the cost value is a value on the right side in each prediction mode, in Formulae (31) and (32).
[Formula 35]Cost=SAD(mode)+QP0(QP)·SAD0(mode)  (35)
Noted the following formula may be applied in place of Formula (35).
[Formula 36]Cost=SATD(mode)+QP0(QP)·SATD0(mode)  (36)
Regarding such encoding processing based on various prediction modes, for example, Japanese Unexamined Patent Application Publication No. 2005-151017 proposes a method in which processing of selecting a best mode is simplified by narrowing prediction modes based on a resolution or the like of an image for processing.
Meanwhile, the processing of selecting a best prediction mode from a multitude of prediction modes contain an issue of expanded computational complexity. Particularly, in the intra 4×4 mode, intra 8×8 mode, and intra 16×16 mode, cost values have to be calculated for 9, 9, and 4 prediction directions respectively per a block, and thus enormous computation complexity is required for calculation of the cost values.